Passeio Aleatório Simétrico

Esperança

Como \(X_{n}\) é a soma de variáveis aleatórias \(U_{i}\), a esperança de \(X_{n}\) pode ser obtida: \[ \mathbb{E}[X_{n}]=\mathbb{E}[\sum_{i=1}^{n}U_{i}]=\sum_{i=1}^{n}\mathbb{E}[U_{i}] \] Como \(U_{i}\) assume 1 e -1 ambos com probabilidade \(\frac{1}{2}\), temos: \[ \mathbb{E}[U_{i}]=1\times\frac{1}{2}+(-1)\times\frac{1}{2}=0 \] Portanto a esperança de \(X_{n}\) é igual a zero.

Isso significa que, em média, o processo não tende para um lado específico, mas está igualmente “distribuído” ao redor da origem.

Definição de Matriz de Transição

A matriz de transição \(P\) descreve as probabilidades de transição de um estado \(i\) para outro estado \(j\) em um único passo.

Para o passeio aleatório com espaço de estados \(S= \mathbb{Z}\), temos:

\[ P_{i,j} = \begin{cases} p & \text{se } j = i+1, \\ 1-p & \text{se } j = i-1, \\ 0 & \text{caso contrário.} \end{cases} \]

Representação da Matriz \(P\)

Se \(S = \{0, 1, 2 ,3 ,4\}\) um espaço de estados discreto finito, a matriz de transição \(P\) é dada por:

\[ P = \begin{bmatrix} P_{0,0} & P_{0,1} & P_{0,2} & P_{0,3} & P_{0,4} \\ P_{1,0} & P_{1,1} & P_{1,2} & P_{1,3} & P_{1,4} \\ P_{2,0} & P_{2,1} & P_{2,2} & P_{2,3} & P_{2,4} \\ P_{3,0} & P_{3,1} & P_{3,2} & P_{3,3} & P_{3,4} \\ P_{4,0} & P_{4,1} & P_{4,2} & P_{4,3} & P_{4,4} \end{bmatrix}. \]

Para o nosso caso de passeio aleatório finito \(S =\{0,1,2,...,N\}\) a matriz de transição será uma matriz \((N+1)\times(N+1)\).

também precisamos definir umas condições de contorno:

• Contorno reflexivo: Se estamos no estado extremo \(i=0\) ou \(i=N\), o sistema “rebate” e não sai do espaço

\[ P = \begin{bmatrix} 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 0.5 & 0.5 \end{bmatrix}. \]

• Contorno absorvente: O sistema permanece no estado extremo \(i=0\) ou \(i=N\)

\[ P = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 0 & 1 \end{bmatrix}. \]

Vamos definir o Contorno Reflexivo para estudo e apresentação deste trabalho, pois note que definindo o contorno da matriz de transição sofremos alteração no problema todo como um geral e suas distribuições.

\[ P = \begin{bmatrix} 1-p & p & 0 & \dots & 0 \\ 1-p & 0 & p & \dots & 0 \\ 0 & 1-p & 0 & \dots & p \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & \dots & 0 & 1-p & p \\ 0 & \dots & 0 & 1-p & p \end{bmatrix}. \]

Propriedades da Matriz de Transição: Estocasticidade, Simetria (para \(p=1/2\)), Sparsa , Aperiodicidade, Irredutibilidade, Estacionaridade

Como estamos trabalhando com passeio aleatório simétrico, temos \(p = \frac{1}{2}\). Temos simetria pois as probabilidades de transição para frente \((i + 1)\) e para trás \((i - 1)\) são iguais! Consequentemente, temos para assimétrico \(p \neq \frac{1}{2}\).

Podemos analisar as matrizes dada a simetria e assímetria associadas e suas propriedades!

Exemplo para \(N = 3\) (espaço \(S = \{0, 1, 2, 3\}\))

Com \(p = 0.5\) e contornos reflexivos: \[ P = \begin{bmatrix} 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 0.5 & 0.5 \end{bmatrix}. \] Propriedades Específicas: Recorrência, Distribuição Assintótica

Caso passeio Aleatório Assimétrico \(p \neq \frac{1}{2}\)

Com \(p = 0.66\) e contornos reflexivos: \[ P = \begin{bmatrix} 0.33 & 0.66 & 0 & 0 \\ 0.33 & 0 & 0.66 & 0 \\ 0 & 0.33 & 0 & 0.66 \\ 0 & 0 & 0.33 & 0.66 \end{bmatrix}. \] Propriedades Específicas: Têndencia Direcional, Irreversibilidade

Exemplos de transição a n passos:

É interessante observar o comportamento da matriz de transição para um número grande de passos. Vamos considerar o caso de \(N = 3\) e \(p = 0.5\) e calcular a matriz de transição para \(n = 2\) e \(n = 3\), \(n=4\) e \(n=500\).

Matriz \(P^2\) (transição em 2 passos):

\[ P^2 = \begin{bmatrix} 0.5 & 0.25 & 0.25 & 0 \\ 0.25 & 0.5 & 0 & 0.25 \\ 0.25 & 0 & 0.5 & 0.25 \\ 0 & 0.25 & 0.25 & 0.5 \end{bmatrix}. \]

O que podemos observar aqui?

• As probabilidades de transição são mais equilibradas em relação à matriz original \(P\), pois a random walk ja teve chance de “se mover” por mais de um passo.
• Apesar de se espalhar o sistema ainda não atingiu uma distribuição homogênea. A cadeia ainda possui alguma “memória” do estado inicial.
• O sistema começa a ter uma chance maior de ir para estados não-adjacentes, mas ainda há certa “preferência” por estados adjacentes.

Matriz \(P^3\) (transição em 3 passos):

\[ P^3 = \begin{bmatrix} 0.375 & 0.375 & 0.125 & 0.125 \\ 0.375 & 0.125 & 0.375 & 0.125 \\ 0.125 & 0.375 & 0.125 & 0.375 \\ 0.125 & 0.125 & 0.375 & 0.375 \end{bmatrix}. \]

O que podemos observar aqui?

• As probabilidades estão mais equilibradas entre os estados.
• Apesar de ainda não ser completamente uniforme, da para notar uma maior “mistura” entre os estados.
• O sistema está começando a perder memória do seu estado inicial, a cadeia está mais “descentralizada” e as probabilidades começam a se espalhar mais uniformemente.

Matriz \(P^4\) (transição em 4 passos):

\[ P^4 = \begin{bmatrix} 0.375 & 0.25 & 0.25 & 0.125 \\ 0.25 & 0.375 & 0.125 & 0.25 \\ 0.25 & 0.125 & 0.375 & 0.25 \\ 0.125 & 0.25 & 0.25 & 0.375 \end{bmatrix}. \]

O que podemos observar aqui?

• Após 4 passos, as probabilidades de transição entre os estados estão quase equilibradas, com uma leve tendência para os estados vizinhos
• O sistema parece estar alcançando um comportamento de distribuição estacionárioa (ou próxima disso pelo menos)
• Esse é um comportamento típico de uma cadeia de Markov que está perdendo sua “memória” do estado inicial e se aproximando de uma distribuição a longo prazo

Matriz \(P^{500}\) (transição em 500 passos):

\[ P^{500} = \begin{bmatrix} 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 \end{bmatrix}. \]

O que podemos observar aqui?

• A matriz \(P^{500}\) nos mostra que, após um grande número de passos as probabilidades de transição entre os estados estão completamente equilibradas e uniformes
• Cada estado tem uma probabilidade de transitar para qualquer outro estado. Portanto depois de muitos passos a cadeia de Markov perde sua memória do estado inicial e atinge um estado de equilíbrio estacionário
• Essa distribuição uniforme de probabilidades é característica de uma cadeia de Markov irreducível e aperiódica, onde todos os estados são acessíveis e a cadeia não possui ciclos regulares.

Distribuição invariante

A distribuição invariante de uma cadeia de Markov como vista em aula é uma distribuição de probabilidade \(\pi = (\pi_i)\) tal que, ao aplicarmos a matriz de transição \(P\), a distribuição permanece inalterada tal que: \[ \pi P = \pi. \]

Em nosso contexto de apresentação (passeio aleatório simétrico reflexivo) a “particula” pode explorar todo o espaço \(S = \{0,1,...,N\}\) de forma contínuam retornando os estados após atingir os extremos.

Nesse caso então a distribuição invariante neste caso será uniforme (pois note que o passeio é simétrico).

Se \(\pi = [\pi_0, \pi_1, \dots, \pi_N]\) representa a distribuição invariante:

então

\[ \pi_i = \frac{1}{N+1}, \quad \forall i \in \{0, 1, \dots, N\}. \]

Note que a distribuição reflete o fato de que ao longo prazo todos os estados têm a mesma probabilidade de serem visitados como confirmamos com as matrizes de transição acima.

Para o nosso exemplo de espaço discreto finito \(S={0, 1, 2,3}:\) \[ P = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{bmatrix} \ \]

A distribuição invariante será:

\[ \pi = \left( \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4} \right) \]

vc Ao longo prazo a partícula estará em qualquer estado com a mesma probabilidade

Distribuição Limite

A distibuição limite de uma cadeia de Markov é o estado ao qual a distribuição converge muitas iterações da matriz da transição, isto é, quando \(n \to \infty\) independente da distribuição inicial \(\pi^{(0)}\)

\[ \lim_{n \to \infty} P^n(i, j) \]

Como vimos em aula, um espaço de estados finitos, a distribuição limite será igual à distribuição invariante.

Tendo isso em mente, no nosso caso reflexivo a distribuição limite coincide com a distribuição invariante:

\[ \lim_{t \to \infty} P(X_t = i) = \pi_i = \frac{1}{N+1}, \quad \forall i. \]

Isso acontece por que o controno reflexivo permite que o sistema continue a se misturar e alcançar equilíbrio uniforme.

Temos com isso algumas propriedades importantes para esse tipo de random walk:

• Reversibilidade : O passeio com contorno reflexivo é reversível, ou seja temos equilbrio de probabilidade tal que:

\[ \pi_i P_{ij} = \pi_j P_{ji}, \quad \forall i, j. \]

• Mixing Time: O tempo necessário para atingir a distribuição uniforme (limite) depende do tamanho do espaçço \(N + 1\)
• Propriedade de Confinamento : O reflexivo evita que a partícula “escape”, garantindo que a soma das probabilidades seja sempre 1.

Muda muita coisa se estamos falando de contorno absorvente? Muda sim, e muito!

Se analisarmos o contexto do passeio aleatório simétrico com contorno absorvente, vemos que as regras de transições são modificadas, de modo que, ao atingir um dos estados do contorno (\(i=0\) ou \(i=N\)), o processo não pode mais sair desse estado.

Então ao vermos a distribuição estacionária, temos que ver diferente do sentido clássico pois o sistema pode ser absorvido em \(0\) ou \(N\). No entando podemos descrever a probabilidade de absorção em cada estado absorvente.

Então suponhamos que o passeio comece no estado \(i (1 \leq i \leq N-1)\).

• \(P^{(0)}_i\) -> Probabiliadde do passeio ser absorvido no estado 0
• \(P^{(N)}_i\) -> Probabiliadde do passeio ser absorvido no estado N

Isso pode ser modelado pelas equações de probabilidades de absorção.

As equações de recorrência de \(P^{(0)}_i\) e \(P^{(N)}_i\) são dadas por:

\[ P^{0}_i = \frac{1}{2} P_{i-1}^{(0)} + \frac{1}{2} P_{i+1}^{(0)} \]

com as condições de contorno:

\[ P_0^{(0)} = 1, \quad P_N^{(0)} = 0. \]

fica análogo a probabilidade de absorção em \(N\):

\[ P_i^{(N)} = \frac{1}{2} P_{i-1}^{(N)} + \frac{1}{2} P_{i+1}^{(N)} \]

com as condições de contorno:

\[ P_0^{(N)} = 0, \quad P_N^{(N)} = 1. \]

Essas equações resolvidas de forma analítica resultam em soluções que descrevem a probabilidade de absorção de qualquer estado \(i\).

Para um \(P^{0}_i\) (probabilidade de ser absorvido no estado 0)

\[ P_i^{(0)} = \frac{N - i}{N}. \]

Para um \(P^{N}_i\) (probabilidade de ser absorvido no estado N)

\[ P_i^{(N)} = \frac{i}{N}. \]

Quando falamos agora da distribuição limite falamos do passeio ser absorvido em um dos estados de contorno, dessa forma o processo termina. Então a distribução limite estará concentrada nas probabilidades de absorção \(0\) e \(N\)

E as probabilidades são as mesmas dadas acima para \(P^{0}_i\) e \(P^{N}_i\).

Essas probabilidades determinam a distribuição limite do processo quando o número de passos tende para o infinito, pois o processo se estabiliza no estado absorvente após um nímero suficiente de transições.

Random Walk unidimencional e simétrica em \(S= \mathbb{Z}\)

Como a cadeia é irredutível, a análise do período do estado 0 se aplica a todos os estados da cadeia. Observamos que é impossível retornar ao estado 0 após um número ímpar de passos. Para retornar ao estado 0, o passeio precisa equilibrar o número de movimentos para a direita e para a esquerda, ou seja, “ganhar” n vezes e “perder” n vezes, o que só é possível após 2n passos. Isso implica que o processo é periódico com período 2, pois os retornos à origem ocorrem sempre após um número par de passos.

Isso prejudica a análise de recorrência e transitoriedade, limitando a capacidade de interpretar ou prever padrões de longo prazo. Segundo o livro de Frank Spitzer: Principles of Random Walk, um passeio aleatório periódico é um processo “mal formulado” porque as restrições impostas pela periodicidade dificultam o estudo de propriedades essenciais, como o comportamento de longo prazo e a convergência para distribuições estacionárias.

Transformando um passeio aleatório periódico em aperiódico:

Spitzer ressalta que, em termos da teoria dos grupos, todo passeio periódico pode ser reduzido a um caso aperiódico porque o grupo subjacente \(S\) é isomorfo a um grupo \(\bar{S}\) de dimensão apropriada. Isso significa que, mesmo que o passeio seja originalmente periódico, existe uma maneira de reestruturar \(S\) para alinhar o passeio com uma configuração aperiódica.

Um exemplo disso, é o caso em que trabalhamos com passeios aleatórios simétricos em \(S = \{0, 1,...,N\}\) com bordas reflexivas, a introdução dessas bordas elimina a periodicidade do processo. Isso ocorre porque,ao atingir os limites N , o passeio é refletido, impedindo que ele siga o padrão regular de tempos de retorno típico de processos periódicos. Essa característica permite que o processo fique nos estados 0 ou N por um tempo arbitrário, tornando-o aperiódico.

Vamos simular a trajetória da matriz de transição que estamos trabalhando para verificar a aperiodicidade

\[ P = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{bmatrix} \ \]

Podemos verificar que o processo atinge o estado 0 em tempos arbitrários. O que indica a aperíodicidade do processo.

Características desse processo:

• irredutível

• recorrente positiva

• aperiódica

Como o processo possui essas características podemos afirmar que estamos trabalhando com uma cadeia ergódica, então o processo terá as seguintes propriedades:

• Terá apenas uma distribuição estacionária que é igual a distribuição limite: \(lim_{n \to \infty} P^n(i, j) = \pi_j\)

• O tempo médio de retorno ao estado \(i\), denotado por \(\mathbb{E}_i[T_i]\), é inversamente proporcional à probabilidade estacionária \(\pi_i\): \(\mathbb{E}_i[T_i] = \frac{1}{\pi_i}\)

• A frequência relativa de visitas a um estado \(i\) ao longo do tempo converge para \(\pi_i\): \(\frac{\text{Número de visitas a } i}{n} \to \pi_i \quad \text{quase certamente}\)

Tempo de Primeira Parada (Primeira Visita ao Estado 3):

O tempo de primeira visita ao estado \(j\) a partir de um estado inicial \(i\) é definido como o menor número de passos necessários para o passeio atingir \(j\) pela primeira vez. Denotamos esse tempo como \(T_j\), onde: \(T_j = \min \{ n \geq 1 \mid X_n = j \}\)

Vamos analisar o comportamento da primeira chegada ao estado 3

n_rep <- 1000
n_steps <- 100
Ts <- numeric(n_rep)

for (i in 1:n_rep) {
  trajetoria <- markov(init, P, n_steps)
  times <- 0:n_steps
  Ts[i] <- min(times[trajetoria == 4])
}

cat("Em média o processo visitará o estado 3 pela primeira vez no tempo: ",mean(Ts))

## Em média o processo visitará o estado 3 pela primeira vez no tempo:  11.893

T_data <- data.frame(Ts = Ts)

ggplot(T_data, aes(x = Ts)) +
  geom_histogram(aes(y = ..density..), bins = 30, fill = "blue", alpha = 0.7) +
  geom_density(color = "red", size = 1) +
  labs(
    title = "Distribuição do Tempo de Primeira Chegada ao Estado 3",
    x = "Tempo de Chegada (Ts)",
    y = "Densidade"
  ) +
  theme_minimal()

Tempo médio de retorno ao estado 3

Vimos anteriormente que este é um processo ergódico, portanto, esperamos que o tempo médio de retorno ao estado seja inversamente proporcional à probabilidade estacionária \(\pi_i\):

\(\mathbb{E}_i[T_i] = \frac{1}{\pi_i}\)

Portanto, esperamos que o tempo médio de retorno será de aproximadamente 4.

return_times <- numeric(n_rep)

for (i in 1:n_rep) {
  trajetoria <- markov(init, P, n_steps)
  visits <- which(trajetoria == 4)
  if (length(visits) > 1) {
    return_times[i] <- visits[2] - visits[1]
  } else {
    return_times[i] <- NA
  }
}

return_times_clean <- return_times[!is.na(return_times)]
tempo_medio_retorno <- mean(return_times_clean)

cat("Tempo médio de retorno ao estado 3:", tempo_medio_retorno, "\n")

## Tempo médio de retorno ao estado 3: 3.921

Tempo da k-ésima passagem pelo estado 3

set.seed(150)

n_steps <- 1000
n_rep <- 1000
k_values <- c(2, 5, 10)
resultados <- list()

tempo_k_esima_passagem <- function(trajetoria, k, estado) {
  visitas <- which(trajetoria == estado)
  if (length(visitas) >= k) {
    return(visitas[k])
  } else {
    return(NA)
  }
}

for (k in k_values) {
  tempos <- numeric(n_rep)
  for (i in 1:n_rep) {
    trajetoria <- markov(init = c(1, 0, 0, 0), P, n_steps)
    tempos[i] <- tempo_k_esima_passagem(trajetoria, k, estado = 4)
  }
  resultados[[as.character(k)]] <- tempos[!is.na(tempos)]
}



resultados_long <- data.frame(
  k = rep(k_values, times = sapply(resultados, length)),
  tempos = unlist(resultados)
)

ggplot(resultados_long, aes(x = tempos, fill = factor(k))) +
  geom_density(aes(color = factor(k)), size = 1) +
  labs(
    x = "Tempo (n)",
    y = "Densidade",
    fill = "Valor de k",
    color = "Valor de k"
  ) +
  theme_minimal()

medias <- sapply(resultados, mean)

for (k in names(medias)) {
  cat("Média do tempo da", k, "-ésima passagem pelo estado 3:", medias[k], "\n")
}

## Média do tempo da 2 -ésima passagem pelo estado 3: 16.736 
## Média do tempo da 5 -ésima passagem pelo estado 3: 29.98 
## Média do tempo da 10 -ésima passagem pelo estado 3: 50.255

O tempo médio entre visitas consecutivas a um estado é finito e inversamente proporcional à probabilidade estacionária do estado. No caso do estado 3, com \(\pi_3 = \frac{1}{4}\), o tempo médio de retorno ao estado é:

\(\mathbb{E}[T_3] = \frac{1}{\pi_3} = 4\)

Essa propriedade implica que, para valores de \(k\) maiores, o tempo da \(k\)-ésima passagem ao estado 3 tende a crescer linearmente com \(k\), pois o intervalo entre as passagens consecutivas permanece estável em média.

Cenário 1

\[ P = \begin{bmatrix} 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 0.5 & 0.5 \end{bmatrix} \]

Podemos facilmente concluir que não faz sentido tratar de probabilidade de absorção nesse passeio aleatório. Exemplo: situação de um sistema de tráfego com os estados representando a intensidade do congestionamento (1 = livre, 4 = congestionado).

Cenário 2

\[ P = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

Neste cenário, podemos notar que temos 2 estados absorventes (1 e 4) e os demais são estados transientes. Essa configuração nos nos permite afirmar não só que há estados transientes como a cadeia como se trata de uma cadeia absorvente, ou seja, a probabilidade do processo ser absorvido é 1. Imaginando na prática podemos pensar nessa matriz como uma representação de um apostador que para de jogar ao ficar sem dinheiro, estado 1, ou quando chega em determinado valor, estado = 4.

Com isso, faz sentido calcularmos as probabilidades de absorção dos estados absorventes condicionada ao estado inicial do processo;

m <- matrix(c(1.0, 0.0, 0.0, 0.0,
              0.5, 0.0, 0.5, 0.0,
              0.0, 0.5, 0.0, 0.5,
              0.0, 0.0, 0.0, 1.0), ncol = 4, byrow = TRUE)
mc <- new("markovchain", states = letters[1:4], transitionMatrix = m)
absorptionProbabilities(mc)

##           a         d
## b 0.6666667 0.3333333
## c 0.3333333 0.6666667

Random walk em duas e três dimensões

“A drunk man will find his way home, but a drunk bird may get lost forever.” – Shizuo Kakutani

Livros relacionados

• Mercado Financeiro:
  • Predição do preço de ações;
  • Simulação de risco;
• Física e Química:
  • Propagação de calor;
  • Mutações genéticas;
  • Movimento de moléculas;
  • Formação de polímeros;
• Biologia:
  • Movimentos de animais;
• Computação:
  • PageRank;
  • Recomendações em Redes Sociais;

Aplicações mais úteis

Quantum Cloud, Londres

1

Considere um passeio aleatório simétrico (\(p = 0.5\)) Dado que \(X_0 = 0\), encontre a probabilidade de retorno em \(t = 2n\), ou seja, \(P(X_{2n} = 0)\).

*** Resolução *** Para retornar a um estado precisamos que o número de passos a direita seja igual ao número de passos a esquerda.

Portanto a probabilidade de um caminho de retorno seria; \[ p^n(1-p)^n \] Se tratando de um passeio aleatório simétrico essa expressão é equivalente a; \[ (0.5)^n(0.5)^n = (0.5)^{2n} \]

Para chegar a probabilidade precisamos multiplicar pelo número de sequências (combinações de passos) que satisfazem a condição de termos o mesmo número passos para cada lado: \[ \binom{2n}{n} = \frac{2n!}{n!(2n-n)!} \]

Portanto; \[ P(X_{2n} = 0) = \binom{2n}{n}(0.5)^{2n} \]

Note ainda que como \(t\) é uma contagem do número de passos e consideramos apenas passos completos temos que \(t \in \mathbb{N}\).

Logo para t ímpar a combinação não está definida, assim; \[ P(X_{2n} = 0) = \binom{t}{\frac{t}{2}}p^{\frac{t}{2}}(1-p)^{\frac{t}{2}} = 0 \] Concluímos com isso que é impossível voltar ao mesmo estado com um número ímpar de passos.

2

Usando R, simule e plote um passeio aleatório simétrico em uma dimensão com \(n\) passos depois responda: a) Houveram quantos retornos à origem? Qual foi a distância máxima da origem? b) Repita a simulação \(N\) vezes. Considere \(F\) como a posição final do passeio, plote a distribuição de \(F\). c) Considerando a simulação do item anterior, qual foi o tempo médio de 1° retorno à origem?

*** Resolução ***

sim_random_walk <- function(n) {

    steps <- sample(c(-1, 1), size = n, replace = TRUE, prob = c(.5, .5))
    return(cumsum(steps))
}

n_steps <- 1000
n_rep   <- 500

first_walk <- sim_random_walk(n_steps)
df         <- data.frame(step = 1:n_steps, position = first_walk)

ggplot(df, aes(x = step, y = position)) +
    geom_line() +
    labs(title = "simulação de 1 passeio aleatório",
       x     = "Passo",
       y     = "Posição") +
    theme_minimal()

Contando retornos ao ponto de origem, no caso \(X_0 = 0\) e a distância máxima do ponto inicial;

returns_to_0 <- sum(first_walk == 0)
max_dist     <- max(abs(first_walk))

cat("Número de retornos à origem: ", returns_to_0, "\n")

## Número de retornos à origem:  11

cat("Distância máxima alcançada do ponto inicial: ", max_dist, "\n")

## Distância máxima alcançada do ponto inicial:  24

Passo em que ocorreu a primeira volta a origem;

first_return <- min(which(first_walk == 0))

if (is.finite(first_return)) {
    first_return
} else {
    cat("Não houve retorno.\n")
}

## [1] 2

Distribuição da posição final considerando 500 repetições;

all_walks    <- list()
return_times <- c()

for (i in 1:n_rep){

    all_walks[[i]]  <- sim_random_walk(n_steps)

    if (is.finite(min(which(all_walks[[i]][-1] == 0)))) {
        return_times[i] <- min(which(all_walks[[i]][-1] == 0))
    } else {
        return_times[i] <- 0
    }
}

df <- data.frame(step = rep(1:n_steps, times = n_rep),
                 position = unlist(all_walks),
                 walk = rep(1:n_rep, each = n_steps))

ggplot(df, aes(x = step, y = position, group = walk, color = as.factor(walk))) +
    geom_line(alpha = 0.7) +
    labs(title = "Trajetórias Simuladas",
         x = "Passo",
         y = "Posição",
         color = "Passeio") +
    theme_minimal() +
    theme(legend.position = "none")

df <- data.frame(final_pos = sapply(all_walks, function(walk) tail(walk, 1)))

ggplot(df, aes(x = final_pos)) +
    geom_histogram(fill = "lightblue", alpha = 0.7) +
    labs(title = "Distribuição da posição final",
         x     = "F",
         y     = "") +
    theme_minimal()

Estatísticas de 1° retorno ao ponto inicial:

## Média do tempo de retorno: 30.49896 passos.

## 17 caminhos não retornaram ao estado zero.

## Isso representa 0.034 do total de simulações.